package leetcode_core.leetcode_6;

import org.junit.Test;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 功能描述
 *
 * @author: 张庭杰
 * @date: 2023年01月20日 13:34
 */
public class MovingCount {
    private int[][] memo;
    private int[][] step=new int[][]{{0,1},{1,0}};
    public int movingCount(int n, int m, int k) {
        memo = new int[n][m];
        //先对格子进行预处理
        int x = 0,y=0,sum = 0;
        for(int i = 0;i<=n-1;i++){
            for(int j = 0;j<=m-1;j++){
                sum = 0;x = i;y = j;
                while(x!=0){
                    sum += x%10;
                    if(sum > k){break;}
                    x/=10;
                }
                while (y!=0){
                    sum += y%10;
                    if(sum > k){break;}
                    y/=10;
                }
                if(sum > k){memo[i][j] = 1;}
            }
        }
        //预处理完毕,准备搜索
        //广搜队列
        Queue<int[]> q = new LinkedList<>();
        //初始化搜索队列
        q.offer(new int[]{0,0});memo[0][0] = 1;
        int count = 1;
        while(!q.isEmpty()){
            int[] head = q.poll();
            for(int j = 0;j<2;j++){
                int tx = head[0]+step[j][0];
                int ty = head[1]+step[j][1];
                if(tx < 0 || tx >= n || ty <0 || ty>= m || memo[tx][ty] == 1 ){
                    continue;
                }
                q.offer(new int[]{tx,ty});
                memo[tx][ty] = 1;
                count++;
            }
        }
        return count;
    }

    @Test
    public void test(){
        System.out.println(movingCount(2,3,1));
        System.out.println(movingCount(3,1,0));
    }

}
